//给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
//
// 给出数字到字母的映射如下（与电话按键相同）。注意 Array.prototype.unshift 不对应任何字母。
//
//
//
//
//
// 示例 Array.prototype.unshift：
//
//
//输入：digits = "23"
//输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
//
//
// 示例 2：
//
//
//输入：digits = ""
//输出：[]
//
//
// 示例 3：
//
//
//输入：digits = "2"
//输出：["a","b","c"]
//
//
//
//
// 提示：
//
//
// 0 <= digits.length <= 4
// digits[i] 是范围 ['2', '9'] 的一个数字。
//
//
// Related Topics 哈希表 字符串 回溯与递归 👍 2384 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function letterCombinations(digits: string): string[] {
    if (digits === '') return [];
    // 映射字典
    const strMap: { [index: string]: string[] } = {
        1: [],
        2: ['a', 'b', 'c'],
        3: ['d', 'e', 'f'],
        4: ['g', 'h', 'i'],
        5: ['j', 'k', 'l'],
        6: ['m', 'n', 'o'],
        7: ['p', 'q', 'r', 's'],
        8: ['t', 'u', 'v'],
        9: ['w', 'x', 'y', 'z'],
    }
    const resArr: string[] = [];
    function backTracking(digits: string, curIndex: number, route: string[]): void {
        if (curIndex === digits.length) {
            resArr.push(route.join(''));
            return;
        }
        // 通过curIndex来控制循环条件结束，同时也控制了当前要for循环的数组
        let tempArr: string[] = strMap[digits[curIndex]];
        for (let i = 0, length = tempArr.length; i < length; i++) {
            route.push(tempArr[i]);
            backTracking(digits, curIndex + 1, route);
            route.pop();
        }
    }
    backTracking(digits, 0, []);
    return resArr;
};
//leetcode submit region end(Prohibit modification and deletion)
